import hashlib
import heapq
import random

import time
import operator
import asyncio
import math
from itertools import chain
from collections import OrderedDict
from kademlia.utils import shared_prefix, bytes_to_bit_string
from kademlia.node import Node
from kademlia.protocol import KademliaProtocol


class KBucket:
    # k桶的结构
    def __init__(self, rangeLower, rangeUpper, ksize, replacementNodeFactor=5):
        self.range = (rangeLower, rangeUpper
                      )  # range： K桶距离范围，代表桶里存储的节点与该节点的距离范围[2^i,2^(i+1)
        self.nodes = OrderedDict(
        )  # nodes：有序字典存储K桶的节点，输出顺序和插入顺序相同，每个节点node就是一个<key,value>
        self.replacement_nodes = OrderedDict(
        )  # replacement_nodes: 替换节点列表，新节点加入时肯能使用到
        self.touch_last_updated()
        self.ksize = ksize  # ksize: K桶的大小
        self.max_replacement_nodes = self.ksize * replacementNodeFactor
        # max_replacement_nodes: 最大替换节点数量，代表替换节点列表最大容纳的节点数

    def touch_last_updated(self):
        self.last_updated = time.monotonic()  # 返回小数秒内单调时钟，代表k桶的上一次更新时间

    # 返回桶里的所有节点的values
    def get_nodes(self):
        return list(self.nodes.values())

    # 将K桶平分为两个桶one、two
    def split(self):
        midpoint = (self.range[0] + self.range[1]) // 2  # 除2取整
        one = KBucket(self.range[0], midpoint, self.ksize)
        two = KBucket(midpoint + 1, self.range[1], self.ksize)
        nodes = chain(self.nodes.values(), self.replacement_nodes.values())
        for node in nodes:
            bucket = one if node.long_id <= midpoint else two
            bucket.add_node(node)

        return (one, two)

    # 删除节点
    def remove_node(self, node):
        # 如果节点在替换节点字典中，直接删除
        if node.id in self.replacement_nodes:
            del self.replacement_nodes[node.id]
        # 如果节点在现在K桶节点字典中
        if node.id in self.nodes:
            del self.nodes[node.id]  # 先直接从节点字典中删除
            # 如果替换节点字典存在
            if self.replacement_nodes:
                newnode_id, newnode = self.replacement_nodes.popitem(
                )  # 删除替换节点字典中最后的节点，并返回该节点的key和value
                self.nodes[newnode_id] = newnode  # 将上述弹出的节点加入K桶的节点字典中

    # 判断某节点mode是否在rang范围内
    def has_in_range(self, node):
        return self.range[0] <= node.long_id <= self.range[1]

    # 判断节点是不是新节点
    def is_new_node(self, node):
        return node.id not in self.nodes

    # 添加节点
    def add_node(self, node):
        """
        Add a C{Node} to the C{KBucket}.  Return True if successful,
        False if the bucket is full.

        If the bucket is full, keep track of node in a replacement list,
        per section 4.1 of the paper.
        """
        if node.id in self.nodes:  # 如果该节点已经在K桶里面了，则进行删除和更新操作
            del self.nodes[node.id]
            self.nodes[node.id] = node
        elif len(self) < self.ksize:  # 如果不在K桶里，判断k桶是不是没有满，没有的话，则添加节点
            self.nodes[node.id] = node  # 无法向K桶添加节点时，放置到替换节点字典
        else:
            if node.id in self.replacement_nodes:
                del self.replacement_nodes[
                    node.id]  # 首先也要判断替换节点字典中是已经存在，存在的话就先删除

            self.replacement_nodes[node.id] = node  # 将新的节点先存在替换节点字典中
            while len(self.replacement_nodes) > self.max_replacement_nodes:
                self.replacement_nodes.popitem(
                    last=False)  # 当超过阈值时，删除节点字典中前面的节点，从前面开始删除
            return False
        return True

    # 获得k桶深度，即k桶各节点相同前缀的长度
    def depth(self):
        vals = self.nodes.values()
        sprefix = shared_prefix([bytes_to_bit_string(n.id) for n in vals])
        return len(sprefix)

    # 获得K桶头节点存储的值
    def head(self):
        return list(self.nodes.values())[0]

    # 获取id为node_id节点的值，没有找到时返回None
    def __getitem__(self, node_id):
        return self.nodes.get(node_id, None)

    # 获取K桶的长度，即节点字典的长度
    def __len__(self):
        return len(self.nodes)


# 路由表迭代类实现
class TableTraverser:
    def __init__(self, table, startNode):
        index = table.get_bucket_for(startNode)
        table.buckets[index].touch_last_updated()
        self.current_nodes = table.buckets[index].get_nodes()
        self.left_buckets = table.buckets[:index]
        self.right_buckets = table.buckets[(index + 1):]
        self.left = True

    def __iter__(self):
        return self

    def __next__(self):
        """
        Pop an item from the left subtree, then right, then left, etc.
        """
        if self.current_nodes:
            return self.current_nodes.pop()

        if self.left and self.left_buckets:
            self.current_nodes = self.left_buckets.pop().get_nodes()
            self.left = False
            return next(self)

        if self.right_buckets:
            self.current_nodes = self.right_buckets.pop(0).get_nodes()
            self.left = True
            return next(self)

        raise StopIteration


class RoutingTable:
    def __init__(self, protocol, ksize, node):
        """
        @param node: The node that represents this server.  It won't
        be added to the routing table, but will be needed later to
        determine which buckets to split or not.
        """
        self.node = node
        self.protocol = protocol
        self.ksize = ksize
        self.flush()

    # 路由表刷新
    def flush(self):
        self.buckets = [KBucket(0, 2**160, self.ksize)]

    # 把指定位置的k桶一分为二
    def split_bucket(self, index):
        one, two = self.buckets[index].split()
        self.buckets[index] = one
        self.buckets.insert(index + 1, two)

    # 获得所有一个小时没有更新的k桶
    def lonely_buckets(self):
        """
        Get all of the buckets that haven't been updated in over
        an hour.
        """
        hrago = time.monotonic() - 3600  # 1小时前=60*60s=3600s前
        return [b for b in self.buckets if b.last_updated < hrago]

    # 移除联系，在路由表中移除某个节点
    def remove_contact(self, node):
        index = self.get_bucket_for(node)  # 找到路由表中包含node的k桶下标index
        self.buckets[index].remove_node(node)  # 将node从该k桶里面删除

    # 判断是否是新的节点
    def is_new_node(self, node):
        index = self.get_bucket_for(node)  # 找出该节点可能落在的k桶的下标index
        return self.buckets[index].is_new_node(node)  # 判断下标为index的k桶里该节点是否是新节点

    # 添加联系
    def add_contact(self, node):
        index = self.get_bucket_for(node)
        bucket = self.buckets[index]

        # this will succeed unless the bucket is full
        if bucket.add_node(node):
            return
        # ？？？
        # Per section 4.2 of paper, split if the bucket has the node
        # in its range or if the depth is not congruent to 0 mod 5
        if bucket.has_in_range(self.node) or bucket.depth() % 5 != 0:
            self.split_bucket(index)
            self.add_contact(node)
        else:
            asyncio.ensure_future(self.protocol.call_ping(bucket.head()))

    # 获得给定节点node可能落在路由表中第几个K桶里的下标
    def get_bucket_for(self, node):
        """
        Get the index of the bucket that the given node would fall into.
        """
        for index, bucket in enumerate(self.buckets):
            if node.long_id < bucket.range[1]:
                return index
        # we should never be here, but make linter happy
        return None

    # 找到离节点node最近的k个的邻居
    def find_neighbors(self, node, k=None, exclude=None):
        k = k or self.ksize
        nodes = []
        for neighbor in TableTraverser(self, node):
            notexcluded = exclude is None or not neighbor.same_home_as(exclude)
            if neighbor.id != node.id and notexcluded:
                heapq.heappush(nodes, (node.distance_to(neighbor), neighbor))
            if len(nodes) == k:
                break

        return list(map(operator.itemgetter(1), heapq.nsmallest(k, nodes)))


# 实验一：同样的节点数,不同k值的时间开销（建立了路由表的时间开销）车联网场景下，一个区域里车的数量有限
def main1():
    node_num = 50
    time0 = time.time()
    print("time0:", time0)

    # 生成36个节点
    nodes = []
    for i in range(node_num):
        rid = hashlib.sha1(str(random.getrandbits(255)).encode()).digest()
        node = Node(rid)
        nodes.append(node)

    # 为每个节点初始化路由表，k=8
    routingTables = []
    for i in range(node_num):
        routingTable = RoutingTable(KademliaProtocol, 8, nodes[i])
        routingTables.append(routingTable)

    # 每个节点完善路由表，即k桶的建立
    i = 0

    for node in nodes:
        count = 0
        i += 1
        print("第" + str(i) + "个节点id：" + str(node.long_id))
        # 在路由表中添加其他节点
        for addnode in nodes:
            if (addnode != node):
                time.sleep(random.uniform(0, 0.005))  # 模拟延时
                count += 1
                if (count >= math.log(node_num)):
                    break
                routingTables[i - 1].add_contact(addnode)
        # print(len(routingTables[i - 1].buckets))
        # print(routingTables[i - 1].buckets[0].get_nodes())
    print("time1:", time.time() - time0)


# 不使用DHT时进行广播时，相当于每个节点都需要建立其他节点的路由表（不考虑存节点不在线等其他情况）
def main2():
    node_num = 50
    time2 = time.time()
    print("time2:", time2)

    # 生成10个节点
    nodes = []
    for i in range(node_num):
        rid = hashlib.sha1(str(random.getrandbits(255)).encode()).digest()
        node = Node(rid)
        nodes.append(node)

    # 为每个节点初始化路由表
    routingTables = []
    for i in range(node_num):
        routingTable = []
        routingTables.append(routingTable)
    i = 0
    # 广播默认全广播模式,在环境条件相同情况下，假设通信延时满足0.005(5G端到端小于5ms)
    for node in nodes:
        for addnode in nodes:
            if addnode != node:
                time.sleep(random.uniform(0, 0.005))  # 模拟延时
                routingTables[i].append(addnode)
        i += 1
        print("第" + str(i) + "个节点id：" + str(node.long_id))

    print("time3:", time.time() - time2)


if __name__ == '__main__':
    # main1()
    main2()
